package com.salim.leetcode.$98;

public class ValidateBinarySearchTree {
    public boolean isValidBST(TreeNode root) {
        return !loop(root).stop;
    }

    MaxLeftAndMinRight loop(TreeNode current){
        MaxLeftAndMinRight result = new MaxLeftAndMinRight(current.val);
        //左 左边所有必须小于自己
        if(current.left!=null){
            if(current.left.val>=current.val){
                return result;
            }
            MaxLeftAndMinRight left = loop(current.left);
            if(left.stop){
                return result;
            }
            if(left.min >=current.val||left.max >=current.val){
                return result;
            }
            result.min = Math.min(result.min,Math.min(left.max,left.min));
            result.max = Math.max(result.max,Math.max(left.max,left.min));
        }
        //右 右必须大于自己
        if(current.right!=null){
            if(current.right.val<=current.val){
                return result;
            }
            MaxLeftAndMinRight right = loop(current.right);
            if(right.stop){
                return result;
            }
            if(right.min <=current.val||right.max <=current.val){
                return result;
            }
            result.min = Math.min(result.min,Math.min(right.max,right.min));
            result.max = Math.max(result.max,Math.max(right.max,right.min));
        }
        result.stop = false;
        return result;
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class MaxLeftAndMinRight{
        boolean stop = true;
        int min;
        int max;
        MaxLeftAndMinRight() {}
        MaxLeftAndMinRight(int val) {
            this.min = val;
            this.max = val;
        }
    }
}
